# -*- coding:utf-8 -*-
"""
 64. Minimum Path Sum (Medium)
 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

 说明：每次只能向下或者向右移动一步。

 示例:

 输入:
 [
 [1,3,1],
 [1,5,1],
 [4,2,1]
 ]
 输出: 7
 解释: 因为路径 1→3→1→1→1 的总和最小。

 思路：动态规划类问题。
 因为只能向下或者向右移动一步，我们定义数组 dp[][]，dp[i][j] 为从左上角(0,0)点到点(i,j)的最短距离，则
 dp[i][j] = Min(dp[i][j-1],dp[i-1][j])
  表示当前这个位置(i,j)的最小路径为其左边位置的最小路径（dp[i][j-1]） 和 上面位置的最小路径(dp[i-1][j]) 两者中的较小值。然后按从左到右，从上到下
  遍历完整个网格即可得到到右下角的最短路径:dp[m-1][n-1]；
 
"""
class MinPathSum:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        m = len(grid)
        n = len(grid[0])
        # 初始化 dp 列表
        dp = [[0 for _ in range(n)] for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if i == 0:
                    dp[i][j] = dp[i][j-1] if j > 0 else 0
                else:
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j]) if j > 0 else dp[i-1][j]
                dp[i][j] += grid[i][j]
        return dp[m-1][n-1]

if __name__ == "__main__":
    mp = MinPathSum()
    result = mp.minPathSum([
            [1,3,1],
            [1,5,1],
            [4,2,1]])
    print(str(result))